home *** CD-ROM | disk | FTP | other *** search
/ The CICA Windows Explosion! / The CICA Windows Explosion! - Disc 1.iso / desktop / dibquant.zip / DIBQUANT.C next >
C/C++ Source or Header  |  1994-06-17  |  24KB  |  864 lines
  1. ///////////////////////////////////////////////////////////////////////////
  2. // DIBQuant version 1.0
  3. // Copyright (c) 1993 Edward McCreary.
  4. // All rights reserved.
  5. //
  6. // Redistribution and use in source and binary forms are freely permitted
  7. // provided that the above copyright notice and attibution and date of work
  8. // and this paragraph are duplicated in all such forms.
  9. // THIS SOFTWARE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR
  10. // IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  11. // WARRANTIES OF MERCHANTIBILILTY AND FITNESS FOR A PARTICULAR PURPOSE.
  12. ///////////////////////////////////////////////////////////////////////////
  13. #define STRICT
  14. #include <windows.h>
  15. #include <windowsx.h>
  16. #include <limits.h>
  17. #include <stdio.h>
  18. #include <stdlib.h>
  19. #include <memory.h>
  20.  
  21. #include "dibquant.h"
  22. #include "rgbvtab.h"
  23. #include "local.h"
  24. #include "palette.h"
  25.  
  26. ///////////////////////////////////////////////////////////////////////////
  27. // ordered dither matrix
  28. int     ord_dith[4][4] = {{-7,  1, -5,  3},
  29.               { 5, -3,  7, -1},
  30.               {-4,  4, -6,  2},
  31.               { 8,  0,  6, -2}};
  32.  
  33.  
  34. // instance handle of dll
  35. HINSTANCE hInst;
  36.  
  37. ///////////////////////////////////////////////////////////////////////////
  38. // Main DLL Entry Point
  39. BOOL WINAPI LibMain (HINSTANCE hInstance, WORD wDataSeg,
  40.     WORD wHeapSize, LPSTR lpszCmdLine)
  41.  {
  42.   if(wHeapSize != 0)
  43.    UnlockData(0);
  44.  
  45.   hInst = hInstance;
  46.   return (TRUE);
  47.  }
  48.  
  49. ///////////////////////////////////////////////////////////////////////////
  50. // Exit procedure for DLL
  51. int WINAPI WEP(int nSystemExit)
  52.  {
  53.   switch(nSystemExit)
  54.   {
  55.    case WEP_SYSTEM_EXIT:
  56.     break;
  57.    case WEP_FREE_DLL:
  58.     break;
  59.    }
  60.    return (1);
  61.  }
  62.  
  63. ///////////////////////////////////////////////////////////////////////////
  64. // build buffer space and lookup table
  65. LPQUANT_BUFFER InitLUT()
  66. {
  67.  LPQUANT_BUFFER lpBuffer;
  68.  unsigned long i; 
  69.  unsigned long len;
  70.  
  71.  lpBuffer = (LPQUANT_BUFFER)malloc(sizeof(QUANT_BUFFER));
  72.  if(!lpBuffer)
  73.   return NULL;
  74.   
  75.  // lut for x^2
  76.  for(i=0;i<256;i++)
  77.   lpBuffer->SQR[i] = (long)i*(long)i;
  78.  
  79.  len = (long)COLOR_MAX*(long)COLOR_MAX*(long)COLOR_MAX;
  80.  
  81.  // buffer to store every color in image
  82.  lpBuffer->lpHisto = (LPNode huge *)GlobalAllocPtr(GHND,len*sizeof(LPNode));
  83.  
  84.  return lpBuffer;
  85. }
  86.  
  87. ///////////////////////////////////////////////////////////////////////////
  88. // free memory associated with buffers and luts
  89. void ClearLUT(LPQUANT_BUFFER lpBuffers)
  90. { 
  91.  unsigned long len = (long)COLOR_MAX*(long)COLOR_MAX*(long)COLOR_MAX;
  92.  unsigned long i;
  93.  
  94.  if(lpBuffers->lpHisto)
  95.  {
  96.   for(i=0;i<len;i++)
  97.    if(lpBuffers->lpHisto[i] != NULL)
  98.    {
  99.     free(lpBuffers->lpHisto[i]);
  100.     lpBuffers->lpHisto[i] = NULL;
  101.    } 
  102.   GlobalFreePtr((LPSTR)lpBuffers->lpHisto);  
  103.  }
  104.  free(lpBuffers);
  105. }
  106.  
  107.  
  108. ///////////////////////////////////////////////////////////////////////////
  109. // main procedures, quantize 24-bit dib
  110. LPSTR FAR PASCAL __export QuantizeDIB(LPSTR lpDIB, int nPalette, int nDither,FARPROC lpStatus)
  111. {
  112.  long width,height;
  113.  LPBITMAPINFOHEADER lpbmi;
  114.  LPSTR lpData;
  115.  BYTE huge *lpLine;
  116.  long i,j;
  117.  int r,g,b;
  118.  long dib_width;
  119.  LPSTR lpNewDIB;
  120.  char buffer[80];
  121.  LPQUANT_BUFFER lpBuffer;
  122.  
  123.  // must have adib
  124.  if(!lpDIB)
  125.   return NULL; 
  126.  
  127.  // must be a 24-bit dib
  128.  lpbmi = (LPBITMAPINFOHEADER)lpDIB;
  129.  if(lpbmi->biBitCount != 24)
  130.   return NULL;
  131.  
  132.  // allocate buffers
  133.  lpBuffer = InitLUT();
  134.   if(!lpBuffer)
  135.    return NULL;
  136.  
  137.  // store handle to status indicator callback
  138.  lpBuffer->lpStatus = lpStatus;
  139.   
  140.  width = lpbmi->biWidth;
  141.  height = lpbmi->biHeight;
  142.  dib_width = WIDTHBYTES(24*width);
  143.  
  144.  lpData = FindDIBBits(lpDIB); 
  145.  
  146.  // generate list of all colors if needed      
  147.  if(nPalette != IDX_DEFAULT)      
  148.   for(j=0;j<height;j++)
  149.    {
  150.     lpLine = (BYTE huge *)lpData + dib_width*j;
  151.     i = width;
  152.     if(lpBuffer->lpStatus)
  153.     {
  154.      wsprintf(buffer,"Finding all colors, %d%%",(int)(100.0*((float)j/(float)height)));
  155.      ((STATUS_CAST)lpBuffer->lpStatus)(buffer);
  156.     } 
  157.     while(i--)
  158.     {
  159.      b = (int)*lpLine++;    
  160.      g = (int)*lpLine++;    
  161.      r = (int)*lpLine++;    
  162.      
  163.     add_color(r>>3,g>>3,b>>3,1L,lpBuffer);    
  164.     }  
  165.    }
  166.  
  167.  // call status if needed
  168.  if(lpBuffer->lpStatus)
  169.      ((STATUS_CAST)lpBuffer->lpStatus)("Building new palette...");
  170.  
  171.  switch(nPalette)
  172.  {
  173.   case IDX_MEDIAN:
  174.    m_box(lpBuffer);
  175.   break;
  176.   
  177.   case IDX_POPULARITY:
  178.    pop(lpBuffer);
  179.   break;
  180.   
  181.   case IDX_DEFAULT:
  182.    LoadDefaultPal(lpBuffer);
  183.   break;
  184.   
  185.   default:
  186.    m_box(lpBuffer);
  187.   break;  
  188.  }
  189.  
  190.  lpNewDIB = Dither(lpDIB,nDither,lpBuffer);
  191.  
  192.  ClearLUT(lpBuffer);
  193.  
  194.  return lpNewDIB; 
  195. }
  196.  
  197.  
  198. ///////////////////////////////////////////////////////////////////////////
  199. // dither image
  200. LPSTR __export Dither(LPSTR lpDIB,int nDither,LPQUANT_BUFFER lpBuffer)
  201. {
  202.  LPSTR lpNewDIB;
  203.  LPSTR lpSrcData;
  204.  LPSTR lpDestData;
  205.  long src_dib_width,dest_dib_width;
  206.  LPBITMAPINFOHEADER  lpbmih;
  207.  long width,height;
  208.  BYTE huge *lpSrcLine;
  209.  BYTE huge *lpDestLine;
  210.  long i,j;
  211.  char buffer[80];
  212.  int r,g,b;
  213.  
  214.  lpNewDIB = AllocNewDIB(lpDIB,lpBuffer);
  215.  if(!lpNewDIB)
  216.   return NULL; 
  217.  
  218.  lpSrcData =  FindDIBBits(lpDIB); 
  219.  lpDestData = FindDIBBits(lpNewDIB); 
  220.  
  221.  
  222.  lpbmih = (LPBITMAPINFOHEADER)lpDIB;
  223.  if(lpbmih->biBitCount != 24)
  224.   return NULL;
  225.   
  226.  width = lpbmih->biWidth;
  227.  height = lpbmih->biHeight;
  228.  src_dib_width = WIDTHBYTES(24*width);
  229.  dest_dib_width = WIDTHBYTES(8*width); 
  230.   
  231.   for(j=0;j<height;j++)
  232.    {
  233.     lpSrcLine = (BYTE huge *)lpSrcData + src_dib_width*j;
  234.     lpDestLine = (BYTE huge *)lpDestData + dest_dib_width*j;
  235.     
  236.     if(lpBuffer->lpStatus)
  237.     {
  238.      wsprintf(buffer,"Building new Image, %d%%",(int)(100.0*((float)j/(float)height)));
  239.      ((STATUS_CAST)lpBuffer->lpStatus)(buffer);
  240.     } 
  241.     
  242.     i = width;
  243.     while(i--)
  244.     {    
  245.      b = (int)*lpSrcLine++;     
  246.      g = (int)*lpSrcLine++;     
  247.      r = (int)*lpSrcLine++;     
  248.      
  249.      if(nDither == IDX_JITTER)
  250.       jitter(i,j,&r,&g,&b);
  251.      
  252.      if(nDither == IDX_ORDERED)
  253.      { 
  254.       r += 2*ord_dith[i%4][j%4]; r = CLIP(r); 
  255.       g += 2*ord_dith[i%4][j%4]; g = CLIP(g); 
  256.       b += 2*ord_dith[i%4][j%4]; b = CLIP(b); 
  257.      }
  258.           
  259.      *lpDestLine++ = (BYTE)GetNeighbor(r,g,b,lpBuffer);     
  260.     }  
  261.    }   
  262.    
  263.    if(lpBuffer->lpStatus)
  264.    {
  265.     wsprintf(buffer,"Building new Image, 100%%");
  266.     ((STATUS_CAST)lpBuffer->lpStatus)(buffer);
  267.    } 
  268.  
  269.  return lpNewDIB;
  270. }
  271.  
  272. ///////////////////////////////////////////////////////////////////////////
  273. // build new palette with median cut algorithm
  274. // I didn't write this, if you know who did, please let me know!
  275. void __export m_box(LPQUANT_BUFFER lpBuffer)
  276. {
  277.     int     i, j, max, dr, dg, db;    
  278.     char buffer[80];
  279.     /* force the counts in the corners to be zero */
  280.  
  281.     force( 0,  0,  0, 0L,lpBuffer);
  282.     force(COLOR_MAX-1,  0,  0, 0L,lpBuffer);
  283.     force( 0, COLOR_MAX-1,  0, 0L,lpBuffer);
  284.     force( 0,  0, COLOR_MAX-1, 0L,lpBuffer);
  285.     force(COLOR_MAX-1, COLOR_MAX-1,  0, 0L,lpBuffer);
  286.     force( 0, COLOR_MAX-1, COLOR_MAX-1, 0L,lpBuffer);
  287.     force(COLOR_MAX-1,  0, COLOR_MAX-1, 0L,lpBuffer);
  288.     force(COLOR_MAX-1, COLOR_MAX-1, COLOR_MAX-1, 0L,lpBuffer);
  289.  
  290.     /* assign the 1st eight boxes to be the corners */
  291.     make_box( 0,  0,  0, 0, 1L,lpBuffer);
  292.     make_box(COLOR_MAX-1,  0,  0, 1, 1L,lpBuffer);
  293.     make_box( 0, COLOR_MAX-1,  0, 2, 1L,lpBuffer);
  294.     make_box( 0,  0, COLOR_MAX-1, 3, 1L,lpBuffer);
  295.     make_box(COLOR_MAX-1, COLOR_MAX-1,  0, 4, 1L,lpBuffer);
  296.     make_box( 0, COLOR_MAX-1, COLOR_MAX-1, 5, 1L,lpBuffer);
  297.     make_box(COLOR_MAX-1,  0, COLOR_MAX-1, 6, 1L,lpBuffer);
  298.     make_box(COLOR_MAX-1, COLOR_MAX-1, COLOR_MAX-1, 7, 1L,lpBuffer);
  299.  
  300.     /* set up 9th box to hold the rest of the world */
  301.     lpBuffer->box[8].r0 = 0;
  302.     lpBuffer->box[8].r1 = COLOR_MAX-1;
  303.     lpBuffer->box[8].g0 = 0;
  304.     lpBuffer->box[8].g1 = COLOR_MAX-1;
  305.     lpBuffer->box[8].b0 = 0;
  306.     lpBuffer->box[8].b1 = COLOR_MAX-1;
  307.     squeeze(8,lpBuffer);
  308.  
  309.     /* split the rest of the boxes */
  310.  
  311.     for(i=9; i<256; i++)    
  312.     {
  313.     
  314.      if(lpBuffer->lpStatus)
  315.      {
  316.       wsprintf(buffer,"splitting box %d",i);
  317.       ((STATUS_CAST)lpBuffer->lpStatus)(buffer);
  318.      }     
  319.      
  320.         /* find biggest box */
  321.         max = 8;
  322.         for(j=8; j<i; j++)
  323.             if(lpBuffer->box[j].count > lpBuffer->box[max].count)
  324.                 max = j;
  325.  
  326.         /* decide which side to split the box along, and split it */
  327.  
  328.         dr = lpBuffer->box[max].r1 - lpBuffer->box[max].r0;
  329.         dg = lpBuffer->box[max].g1 - lpBuffer->box[max].g0;
  330.         db = lpBuffer->box[max].b1 - lpBuffer->box[max].b0;
  331.         lpBuffer->box[i] = lpBuffer->box[max];              /* copy info over */
  332.         if(dr>=dg && dr>=db) 
  333.         {          /* red! */
  334.             if(dr==2) 
  335.             {             /* tight squeeze */
  336.                 lpBuffer->box[i].r1 = lpBuffer->box[i].r0;
  337.                 lpBuffer->box[max].r0 = lpBuffer->box[max].r1;
  338.             } else 
  339.             {                /* figure out where to split */
  340.                 j = lpBuffer->box[max].rave;
  341.                 if(j==lpBuffer->box[max].r1)
  342.                     j--;
  343.                 lpBuffer->box[max].r1 = j;
  344.                 lpBuffer->box[i].r0 = j+1;
  345.             }
  346.             squeeze(i,lpBuffer);
  347.             squeeze(max,lpBuffer);
  348.         } 
  349.         else if(dg>=db) 
  350.         {             /* green! */
  351.             if(dg==2) 
  352.             {             /* tight squeeze */
  353.                 lpBuffer->box[i].g1 = lpBuffer->box[i].g0;
  354.                 lpBuffer->box[max].g0 = lpBuffer->box[max].g1;
  355.             } 
  356.             else 
  357.             {                /* figure out where to split */
  358.                 j = lpBuffer->box[max].gave;
  359.                 if(j==lpBuffer->box[max].g1)
  360.                     j--;
  361.                 lpBuffer->box[max].g1 = j;
  362.                 lpBuffer->box[i].g0 = j+1;
  363.             }
  364.             squeeze(i,lpBuffer);
  365.             squeeze(max,lpBuffer);
  366.         } 
  367.         else 
  368.         {                        /* blue! */
  369.             if(db==2) 
  370.             {             /* tight squeeze */
  371.                 lpBuffer->box[i].b1 = lpBuffer->box[i].b0;
  372.                 lpBuffer->box[max].b0 = lpBuffer->box[max].b1;
  373.             } 
  374.             else 
  375.             {                /* figure out where to split */
  376.                 j = lpBuffer->box[max].bave;
  377.                 if(j==lpBuffer->box[max].b1)
  378.                     j--;
  379.                 lpBuffer->box[max].b1 = j;
  380.                 lpBuffer->box[i].b0 = j+1;
  381.             }
  382.             squeeze(i,lpBuffer);
  383.             squeeze(max,lpBuffer);
  384.         }
  385.  
  386.     }       /* end of i loop, all the boxes are found */
  387.  
  388.     /* get palette colors for each box */
  389.     for(i=0; i<256; i++) 
  390.     {
  391.          lpBuffer->red[i] = (lpBuffer->box[i].r0+lpBuffer->box[i].r1)/2;
  392.          lpBuffer->green[i] = (lpBuffer->box[i].g0+lpBuffer->box[i].g1)/2;
  393.          lpBuffer->blue[i] = (lpBuffer->box[i].b0+lpBuffer->box[i].b1)/2;
  394.     }
  395.     for(i=0; i<256; i++)
  396.     {
  397.      lpBuffer->red[i] *= 255;
  398.      lpBuffer->red[i] /= (COLOR_MAX-1);
  399.      lpBuffer->green[i] *= 255;
  400.      lpBuffer->green[i] /= (COLOR_MAX-1);
  401.      lpBuffer->blue[i] *= 255;
  402.      lpBuffer->blue[i] /= (COLOR_MAX-1);
  403.     }
  404. }       /* end of m_box() */
  405.  
  406. ///////////////////////////////////////////////////////////////////////////
  407. // make a 1x1x1 box at index with color rgb count c
  408. void make_box(int r, int g, int b, int index, unsigned long c,LPQUANT_BUFFER lpBuffer)
  409. {
  410.     lpBuffer->box[index].r0 = r;
  411.     lpBuffer->box[index].r1 = r;
  412.     lpBuffer->box[index].g0 = g;
  413.     lpBuffer->box[index].g1 = g;
  414.     lpBuffer->box[index].b0 = b;
  415.     lpBuffer->box[index].b1 = b;
  416.     lpBuffer->box[index].count = c;
  417. }       /* end of make_box
  418.  
  419. /*
  420.     squeeze -- shrink a boxes extremes to fit tightly
  421.  
  422.            if a box is 1x1x1 change its count to 1
  423. */
  424.  
  425. ///////////////////////////////////////////////////////////////////////////
  426. //
  427. void squeeze(int b,LPQUANT_BUFFER lpBuffer)
  428. {
  429.     int     r0, r1, g0, g1, b0, b1;
  430.     long    i, j, k;
  431.     unsigned long count = 0;
  432.     LPNode    ptr;
  433.     DWORD index;
  434.  
  435.     r0 = lpBuffer->box[b].r0;
  436.     r1 = lpBuffer->box[b].r1;
  437.     g0 = lpBuffer->box[b].g0;
  438.     g1 = lpBuffer->box[b].g1;
  439.     b0 = lpBuffer->box[b].b0;
  440.     b1 = lpBuffer->box[b].b1;
  441.  
  442.     lpBuffer->box[b].r0 = COLOR_MAX-1; lpBuffer->box[b].r1 = 0;
  443.     lpBuffer->box[b].g0 = COLOR_MAX-1; lpBuffer->box[b].g1 = 0;
  444.     lpBuffer->box[b].b0 = COLOR_MAX-1; lpBuffer->box[b].b1 = 0;
  445.     lpBuffer->box[b].rave = 0;
  446.     lpBuffer->box[b].gave = 0;
  447.     lpBuffer->box[b].bave = 0;
  448.  
  449.     for(i=r0; i<=r1; i++)
  450.         for(j=g0; j<=g1; j++) 
  451.             for(k=b0; k<=b1; k++) 
  452.             {    
  453.              index = INDEX(i,j,k);
  454.              ptr = lpBuffer->lpHisto[index];
  455.              if(ptr) 
  456.                if(ptr->count>0L) 
  457.                 {
  458.                  lpBuffer->box[b].r0 = MIN(i, lpBuffer->box[b].r0);
  459.                  lpBuffer->box[b].r1 = MAX(i, lpBuffer->box[b].r1);
  460.                  lpBuffer->box[b].g0 = MIN(j, lpBuffer->box[b].g0);
  461.                  lpBuffer->box[b].g1 = MAX(j, lpBuffer->box[b].g1);
  462.                  lpBuffer->box[b].b0 = MIN(k, lpBuffer->box[b].b0);
  463.                  lpBuffer->box[b].b1 = MAX(k, lpBuffer->box[b].b1);
  464.                  lpBuffer->box[b].rave += (unsigned long)i * (unsigned long)ptr->count;
  465.                  lpBuffer->box[b].gave += (unsigned long)j * (unsigned long)ptr->count;
  466.                  lpBuffer->box[b].bave += (unsigned long)k * (unsigned long)ptr->count;
  467.                  count += (unsigned long)ptr->count;
  468.                  }
  469.             }
  470.     /* box is now shrunk */
  471.  
  472.     if(count) 
  473.     {
  474.         lpBuffer->box[b].rave /= count;
  475.         lpBuffer->box[b].gave /= count;
  476.         lpBuffer->box[b].bave /= count;
  477.     }
  478.  
  479.     lpBuffer->box[b].count = MIN(count, COUNT_LIMIT);
  480.  
  481.     if(lpBuffer->box[b].r0 == lpBuffer->box[b].r1 &&
  482.        lpBuffer->box[b].g0 == lpBuffer->box[b].g1 &&
  483.        lpBuffer->box[b].b0 == lpBuffer->box[b].b1) 
  484.     {    /* box is min size */
  485.         lpBuffer->box[b].count = 1L;       /* so it won't get split again */
  486.     }
  487.  
  488. }       /* end of squeeze */
  489.  
  490. ///////////////////////////////////////////////////////////////////////////
  491. //
  492. void add_color(int r, int g, int b, unsigned long c,LPQUANT_BUFFER lpBuffer)
  493. {
  494.     LPNode    ptr;
  495.     unsigned long      ltmp;
  496.     
  497.     DWORD index = INDEX(r,g,b);
  498.     c = MIN(c,COUNT_LIMIT);
  499.     if((ptr = lpBuffer->lpHisto[index]) == NULL)  // new color
  500.     {
  501.       ptr = lpBuffer->lpHisto[index] = (Node *)malloc(sizeof(Node));
  502.       ptr->index = -1;
  503.       ptr->count = c;
  504.     }
  505.     else
  506.     {    
  507.      ltmp = ptr->count;
  508.      ltmp += c;
  509.      ptr->count = MIN(ltmp,COUNT_LIMIT);
  510.     }
  511.     
  512. }       /* end of add_color()*/
  513.  
  514. ///////////////////////////////////////////////////////////////////////////
  515. //
  516. void force(int r, int g, int b, unsigned long c,LPQUANT_BUFFER lpBuffer)
  517. {
  518.     LPNode    ptr;
  519.     DWORD     index;
  520.     
  521.     c = MIN(c,COUNT_LIMIT);    
  522.     index = INDEX(r,g,b);
  523.     
  524.     if((ptr = lpBuffer->lpHisto[index]) == NULL)  // new color
  525.     {
  526.       ptr = lpBuffer->lpHisto[index] = (Node *)malloc(sizeof(Node));
  527.       ptr->index = -1; 
  528.       ptr->count = 0L;
  529.     }
  530.     
  531.     ptr->count = c;
  532.  
  533. }       /* end of force()*/
  534.  
  535.  
  536.  
  537. ///////////////////////////////////////////////////////////////////////////
  538. // popularity sort
  539. void pop(LPQUANT_BUFFER lpBuffer)
  540. {
  541.     int             i, r, g,b;
  542.     LPNode            ptr;
  543.     unsigned long    pal[256];
  544.     DWORD            index;
  545.     DWORD            index_cache = (DWORD)-1;
  546.     LPNode         ptr_cache;
  547.     
  548.     memset(pal,0,sizeof(unsigned long)*256);
  549.     
  550.     /* force corners of rgb color cube out of the running */
  551.     add_color( 0,  0,  0, 0L,lpBuffer);
  552.     add_color(COLOR_MAX-1,  0,  0, 0L,lpBuffer);
  553.     add_color( 0, COLOR_MAX-1,  0, 0L,lpBuffer);
  554.     add_color( 0,  0, COLOR_MAX-1, 0L,lpBuffer);
  555.     add_color(COLOR_MAX-1, COLOR_MAX-1,  0, 0L,lpBuffer);
  556.     add_color( 0, COLOR_MAX-1, COLOR_MAX-1, 0L,lpBuffer);
  557.     add_color(COLOR_MAX-1,  0, COLOR_MAX-1, 0L,lpBuffer);
  558.     add_color(COLOR_MAX-1, COLOR_MAX-1, COLOR_MAX-1, 0L,lpBuffer);
  559.  
  560.     /* force feed the corners into the palette */
  561.     lpBuffer->red[0] =  0; lpBuffer->green[0] =  0; lpBuffer->blue[0] =  0;
  562.     lpBuffer->red[1] = COLOR_MAX-1; lpBuffer->green[1] =  0; lpBuffer->blue[1] =  0;
  563.     lpBuffer->red[2] =  0; lpBuffer->green[2] = COLOR_MAX-1; lpBuffer->blue[2] =  0;
  564.     lpBuffer->red[3] =  0; lpBuffer->green[3] =  0; lpBuffer->blue[3] = COLOR_MAX-1;
  565.     lpBuffer->red[4] = COLOR_MAX-1; lpBuffer->green[4] = COLOR_MAX-1; lpBuffer->blue[4] =  0;
  566.     lpBuffer->red[5] =  0; lpBuffer->green[5] = COLOR_MAX-1; lpBuffer->blue[5] = COLOR_MAX-1;
  567.     lpBuffer->red[6] = COLOR_MAX-1; lpBuffer->green[6] =  0; lpBuffer->blue[6] = COLOR_MAX-1;
  568.     lpBuffer->red[7] = COLOR_MAX-1; lpBuffer->green[7] = COLOR_MAX-1; lpBuffer->blue[7] = COLOR_MAX-1;
  569.     
  570.     
  571.     for(r=0; r<COLOR_MAX; r++)
  572.     {
  573.         for(g=0; g<COLOR_MAX; g++) 
  574.             for(b=0; b<COLOR_MAX; b++) 
  575.             {             
  576.              index = INDEX(r,g,b);
  577.              if(index == index_cache)
  578.               ptr = ptr_cache;
  579.              else
  580.              {
  581.               ptr = lpBuffer->lpHisto[index];
  582.               ptr_cache = ptr;
  583.               index_cache = index;
  584.              }
  585.              
  586.              if(ptr != NULL) 
  587.              {
  588.                 if(ptr->count > pal[255]) 
  589.                 {
  590.                     pal[255] = ptr->count;
  591.                     lpBuffer->red[255] = r;
  592.                     lpBuffer->green[255] = g;
  593.                     lpBuffer->blue[255] = b;
  594.  
  595.                     i = 255;        /* bubble up */
  596.                     while(pal[i]>pal[i-1] && i>8) 
  597.                     {
  598.                         SWAP(pal[i], pal[i-1]);
  599.                         SWAP(lpBuffer->red[i], lpBuffer->red[i-1]);
  600.                         SWAP(lpBuffer->green[i], lpBuffer->green[i-1]);
  601.                         SWAP(lpBuffer->blue[i], lpBuffer->blue[i-1]);
  602.                         i--;
  603.                     }
  604.                 }
  605.                 
  606.              }       /* end of current chain */
  607.             }       /* end of r loop */            
  608.     }    
  609.     for(i=0; i<256; i++)
  610.     {
  611.      lpBuffer->red[i] *= 255;
  612.      lpBuffer->red[i] /= (COLOR_MAX-1);
  613.      lpBuffer->green[i] *= 255;
  614.      lpBuffer->green[i] /= (COLOR_MAX-1);
  615.      lpBuffer->blue[i] *= 255;
  616.      lpBuffer->blue[i] /= (COLOR_MAX-1);
  617.     }
  618.    
  619. }       /* end of pop */
  620.  
  621.  
  622. ///////////////////////////////////////////////////////////////////////////
  623. //
  624. LPSTR AllocNewDIB(LPSTR lpDIB,LPQUANT_BUFFER lpBuffer)
  625. {
  626.  long width,height;
  627.  LPBITMAPINFOHEADER lpbmih;
  628.  LPBITMAPINFO       lpbmi; 
  629.  long i;
  630.  long dest_dib_width;
  631.  LPSTR lpNewDIB;
  632.  DWORD dwSize;
  633.  
  634.  if(!lpDIB)
  635.   return NULL; 
  636.  
  637.  lpbmih = (LPBITMAPINFOHEADER)lpDIB;
  638.  if(lpbmih->biBitCount != 24)
  639.   return NULL;
  640.   
  641.  width = lpbmih->biWidth;
  642.  height = lpbmih->biHeight; 
  643.  dest_dib_width = WIDTHBYTES(8*width); 
  644.  
  645.  dwSize = dest_dib_width*height + ((long)sizeof(BITMAPINFOHEADER) + 
  646.     (long)(256 * sizeof(RGBQUAD)));
  647.  
  648.  lpNewDIB = (LPSTR)GlobalAllocPtr(GHND | GMEM_SHARE,dwSize);
  649.  
  650.  if(!lpNewDIB)
  651.   return NULL;
  652.   
  653.  lpbmih = (LPBITMAPINFOHEADER)lpNewDIB;
  654.  lpbmih->biSize         = sizeof(BITMAPINFOHEADER);
  655.  lpbmih->biWidth        = (DWORD)width;
  656.  lpbmih->biHeight       = (DWORD)height;
  657.  lpbmih->biPlanes       = 1;
  658.  lpbmih->biBitCount     = 8;
  659.  lpbmih->biCompression  = BI_RGB;
  660.  lpbmih->biSizeImage    = (DWORD)dwSize;
  661.  lpbmih->biClrUsed      = 256;
  662.  lpbmih->biClrImportant = 256;
  663.  
  664.  lpbmi = (LPBITMAPINFO)lpNewDIB;
  665.  for(i=0;i<256;i++)
  666.  {
  667.   lpbmi->bmiColors[i].rgbBlue = (BYTE)(lpBuffer->blue[i]);
  668.   lpbmi->bmiColors[i].rgbGreen = (BYTE)(lpBuffer->green[i]);
  669.   lpbmi->bmiColors[i].rgbRed = (BYTE)(lpBuffer->red[i]);
  670.   lpbmi->bmiColors[i].rgbReserved = (BYTE)0;
  671.  }
  672.  
  673.  return lpNewDIB;
  674. }
  675.  
  676. ///////////////////////////////////////////////////////////////////////////
  677. //
  678. int GetNeighbor(int r,int g,int b,LPQUANT_BUFFER lpBuffer)
  679. {
  680.  int bReturn; 
  681.  
  682.   DWORD  index = 0;
  683.   long min_dist = 0;
  684.   long dist = 0;
  685.   int  c;
  686.   int dr,dg,db;
  687.   int i,j,k; 
  688.   LPNode ptr;
  689.   
  690.   index = INDEX((r>>3),(g>>3),(b>>3));
  691.   if( (ptr = lpBuffer->lpHisto[index]) == NULL)
  692.   {
  693.    lpBuffer->lpHisto[index] = ptr = (Node *)malloc(sizeof(Node));
  694.    ptr->count = 0L;
  695.    ptr->index = -1;
  696.   }
  697.   
  698.   if( (bReturn = ptr->index) == -1)
  699.   {   
  700.    ptr->index = 0;
  701.    i = lpBuffer->red[0];
  702.    j = lpBuffer->green[0];
  703.    k = lpBuffer->blue[0];
  704.  
  705.    dr = i - r;
  706.    dg = j - g;
  707.    db = k - b;
  708.    min_dist = lpBuffer->SQR[abs(dr)] + lpBuffer->SQR[abs(dg)] + lpBuffer->SQR[abs(db)];
  709.    
  710.    for(c = 1;c<256;c++)
  711.    {
  712.     i = lpBuffer->red[c];
  713.     j = lpBuffer->green[c];
  714.     k = lpBuffer->blue[c];
  715.    
  716.     dr = i - r;
  717.     dg = j - g;
  718.     db = k - b;   
  719.     dist = lpBuffer->SQR[abs(dr)] + lpBuffer->SQR[abs(dg)] + lpBuffer->SQR[abs(db)];
  720.     
  721.     if(dist < min_dist)
  722.     {
  723.      ptr->index = c; 
  724.      min_dist = dist;
  725.     }
  726.    }
  727.    bReturn = ptr->index;
  728.   }
  729.  return bReturn;
  730. }
  731.  
  732.  
  733. ///////////////////////////////////////////////////////////////////////////
  734. //
  735. void __export jitter(long x, long y, int *r,int *g,int *b)
  736. {
  737.  int p,q;
  738.  int tmp;
  739.  
  740.  tmp = *r;
  741.  if(tmp < 248)
  742.  {
  743.   p = tmp & 7;
  744.   q = jitterx(x,y,0);
  745.   if(p <= q)
  746.    tmp += 8;
  747.    
  748.   q = tmp + jittery(x,y,0);
  749.   if(q >= 0 && q <= 255)
  750.    tmp = q;
  751.   
  752.   *r = tmp & 0xF8;
  753.   }
  754.   
  755.  tmp = *g;
  756.  if(tmp < 248)
  757.  {
  758.   p = tmp & 7;
  759.   q = jitterx(x,y,1);
  760.   if(p <= q)
  761.    tmp += 8;
  762.    
  763.   q = tmp + jittery(x,y,1);
  764.   if(q >= 0 && q <= 255)
  765.    tmp = q;
  766.   
  767.   *g = tmp & 0xF8;
  768.   } 
  769.   
  770.  tmp = *b;
  771.  if(tmp < 248)
  772.  {
  773.   p = tmp & 7;
  774.   q = jitterx(x,y,2);
  775.   if(p <= q)
  776.    tmp += 8;
  777.    
  778.   q = tmp + jittery(x,y,2);
  779.   if(q >= 0 && q <= 255)
  780.    tmp = q;
  781.   
  782.   *b = tmp & 0xF8;
  783.   }
  784. }
  785.  
  786. ///////////////////////////////////////////////////////////////////////////
  787. // 
  788. void __export LoadDefaultPal(LPQUANT_BUFFER lpBuffer)
  789. {
  790.  int *ptr = def_pal; 
  791.  int i;
  792.  
  793.  for(i=0;i<256;i++)
  794.  {
  795.   lpBuffer->red[i] = *ptr++;
  796.   lpBuffer->green[i] = *ptr++;
  797.   lpBuffer->blue[i] = *ptr++; 
  798.  }
  799. }
  800. ///////////////////////////////////////////////////////////////////////////
  801. // 
  802. LPSTR FAR FindDIBBits(LPSTR lpDIB)
  803. {
  804.    return (lpDIB + *(LPDWORD)lpDIB + PaletteSize(lpDIB));
  805. }
  806.  
  807. ///////////////////////////////////////////////////////////////////////////
  808. // 
  809. WORD FAR PaletteSize(LPSTR lpDIB)
  810. {
  811.    /* calculate the size required by the palette */
  812.    if (IS_WIN30_DIB (lpDIB))
  813.       return (DIBNumColors(lpDIB) * sizeof(RGBQUAD));
  814.    else
  815.       return (DIBNumColors(lpDIB) * sizeof(RGBTRIPLE));
  816. }
  817.  
  818. ///////////////////////////////////////////////////////////////////////////
  819. // 
  820. WORD FAR DIBNumColors(LPSTR lpDIB)
  821. {
  822.    WORD wBitCount;  // DIB bit count
  823.  
  824.    /*  If this is a Windows-style DIB, the number of colors in the
  825.     *  color table can be less than the number of bits per pixel
  826.     *  allows for (i.e. lpbi->biClrUsed can be set to some value).
  827.     *  If this is the case, return the appropriate value.
  828.     */
  829.  
  830.    if (IS_WIN30_DIB(lpDIB))
  831.    {
  832.       DWORD dwClrUsed;
  833.  
  834.       dwClrUsed = ((LPBITMAPINFOHEADER)lpDIB)->biClrUsed;
  835.       if (dwClrUsed)
  836.      return (WORD)dwClrUsed;
  837.    }
  838.  
  839.    /*  Calculate the number of colors in the color table based on
  840.     *  the number of bits per pixel for the DIB.
  841.     */
  842.    if (IS_WIN30_DIB(lpDIB))
  843.       wBitCount = ((LPBITMAPINFOHEADER)lpDIB)->biBitCount;
  844.    else
  845.       wBitCount = ((LPBITMAPCOREHEADER)lpDIB)->bcBitCount;
  846.  
  847.    /* return number of colors based on bits per pixel */
  848.    switch (wBitCount)
  849.       {
  850.    case 1:
  851.       return 2;
  852.  
  853.    case 4:
  854.       return 16;
  855.  
  856.    case 8:
  857.       return 256;
  858.  
  859.    default:
  860.       return 0;
  861.       }
  862. }
  863.  
  864.